Knuth-Morris-Pratt 算法的核心为前缀函数，记作 \(\pi(i)\)。 比如 aabaaab 的 最长相等的真前后缀 为 aab，长度为3。 于是对于某位置 j , next[j] 的值是 3, 即有效向后查找。 可以计算出 pattern 串在主串中的每一次出现

长度为 m 的字符串 s 的所有前缀函数的求解算法的总时间复杂度是严格 \(O(m)\)

求解算法是增量算法，可以一边读入字符串，一边求解当前的前缀函数。

时间复杂度 ：

前缀函数至多比前一位 + 1

每次迭代， 当前位 的前缀函数的最大值会减少

前缀函数的 总减少次数 不超过 总增加次数 , and 总增加次数不会超过 m 次，and 总减少次数不超过 m 次。即总迭代次数不超过 m 次。

空间复杂度 ：

用长度为 m 的数组保存前缀函数，and 使用了常数的空间保存了若干变量。

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int n = haystack.size(), m = needle.size();
            if (m == 0) {
                return 0;
            }
            vector<int> pi(m);
            for (int i = 1, j = 0; i < m; i++) {
                while (j > 0 && needle[i] != needle[j]) {
                    j = pi[j - 1];
                }
                if (needle[i] == needle[j]) {
                    j++;
                }
                pi[i] = j;
            }
            for (int i = 0, j = 0; i < n; i++) {
                while (j > 0 && haystack[i] != needle[j]) {
                    j = pi[j - 1];
                }
                if (haystack[i] == needle[j]) {
                    j++;
                }
                if (j == m) {
                    return i - m + 1;
                }
            }
            return -1;
        }
    };

• 求解 next 递推关系

对于 pattern string 的位置 j, 有 next[j] = k

则对于 j + 1 位置，有两种情况

1. if p[k] == p[j], then next[j + 1] = next[j] + 1;
2. if p[k] != p[j], then let k = next[k], if p[k] == p[j], next[j + 1] = k + 1;
3. else goto step 2.

   class Solution {
   public:
       bool kmp(const string& query, const string& pattern) {
           int n = query.size();
           int m = pattern.size();
       vector<int> fail(m, -1);
           for (int i = 1; i < m; ++i) {
               int j = fail[i - 1];
               while (j != -1 && pattern[j + 1] != pattern[i]) {
                   j = fail[j];
               }
               if (pattern[j + 1] == pattern[i]) {
                   fail[i] = j + 1;
               }
           }
           int match = -1;
           for (int i = 1; i < n - 1; ++i) {
               while (match != -1 && pattern[match + 1] != query[i]) {
                   match = fail[match];
               }
               if (pattern[match + 1] == query[i]) {
                   ++match;
                   if (match == m - 1) {
                       return true;
                   }
               }
           }
           return false;
       }
                                                                                                                                                                                                                                                                                                                   
       bool repeatedSubstringPattern(string s) {
           return kmp(s + s, s);
       }
   };